package cn.whdream.datastructure.huffmantree;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 
 * @author admin
 * 哈夫曼数示例
 */
public class HuffmanTreeDemo {
	public static void main(String[] args) {
		int arr[] = {13,7,8,3,29,6,1};
		Node node = createHuffmanTree(arr);
		node.preOrder();
	}
	public static Node createHuffmanTree(int[] arr) {
		List<Node> nodes = new ArrayList<HuffmanTreeDemo.Node>();
		for (int value : arr) {
			nodes.add(new Node(value));
		}
		Collections.sort(nodes);
		System.out.println(nodes);
		while(nodes.size() > 1) {
			//从循环中取出两个节点
			Node leftNode = nodes.get(0);
			Node rightNode = nodes.get(1);
			//将和构建成一个 value，构建一个二叉树
			Node parentNode = new Node(leftNode.value + rightNode.value);
			parentNode.left = leftNode;
			parentNode.right = rightNode;
			System.out.println("left"+leftNode+" right"+rightNode+"par"+parentNode);
			//删除处理后的二叉树
			nodes.remove(leftNode);
			nodes.remove(rightNode);
			//将处理好的node重新加入list
			nodes.add(parentNode);
			Collections.sort(nodes);
		}
		return nodes.get(0);
	}
	private static class Node implements Comparable<Node>{
		int value;
		Node left;
		Node right;
		public Node(int value) {
			super();
			this.value = value;
		}
		public void preOrder() {
			System.out.println(this);
			if (left != null) {
				left.preOrder();
			}
			if (right != null) {
				right.preOrder();
			}
		}
		@Override
		public int compareTo(Node o) {
			return this.value - o.value;
		}
		@Override
		public String toString() {
			return "Node [value=" + value + "]";
		}
		
		
	}
}
